Before jump into the Ordinary Generating Function (OGF), lets take a refreshness with the concept of power series. In mathematics, a power series (in one variable) is an infinite series of the form:
$$\sum_{n=0}^\infty a_n(x-c)^n = a_0 + a_1(x-c)^1 + a_2(x-c)^2 + ... $$where $a_n$ represents the coefficient of the nth term and c is a constant. $a_n$ is independent of x and may be expressed as a function of n (e.g $a_n = \frac{1}{n!}$). This series usually arise as the Taylor series of some known function.
In many situasions c (the center of the series) is equal to zero, for instance when considering a Maclaurin series. In such case, the power series takes the simpler form:
$$\sum_{n=0}^\infty a_n x^n = a_0 + a_1x + a_2x^2 + ...$$Polynomial function:
$$f(x) = x^2 + 2x + 3$$can be expressed as a power series around the center c = 0:
$$f(x) = 3 + 2x + 1x^2 + 0x^3 + 0x^4 + ... $$or around the center c = 1 as:
$$f(x) = 6 + 4(x-1) + 1(x-1)^2 + 0(x-1)^3 + 0(x-1)^4 + ...$$So, one can view that power series as being like polynomials of infinite degree, altough power series are not polynomials.
The geometric series formula:
$$\frac{1}{1-x} = \sum_{n=0}{\infty} x^n = 1 + x + x^2 + x^3 + ..., $$which is valid for $|x| < 1$, is one of the most important examples of a power series, as are the exponential function formula:
$$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ...,$$and the sine and cos formulae in the form Mclaurin series:
$$sin(x) = \sum_{n=0}^{\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!} = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + ...,$$$$cos(x) = \sum_{m=0}^{\infty} \frac{(-1)^n x^{2n}}{(2n)!} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + ...,$$valid for all real x.
Let say we have series of $x$, such that:
$$x^0, x^1, x^2, ..., x^n, ...$$Each x in the power series above has a coefficient $s$, so that the coefficients of the power series are:
$$s_0, s_1, s_2, ..., s_n, ...$$So, we can conclude that there is a correlation of $s_i \rightarrow x^i$
The generating function has main advantage is the power series is a form of rational number. For example:
$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + ...$$has the form with exist multiplier coefficients such that:
$$\frac{1}{1-x} = s_0 1 + s_1 x + s_2 x^2 + s_3 x^3 + ...$$which is the series of coeffiecients:
$$S = 1, 1, 1, 1, ...$$So, the series $S$ has generating function (GF) $\frac{1}{1-x}$
Another example:
$$\frac{1}{{(1-x)}^2} = 1 + 2x + 3x^2 + 4x^2 + ...$$So, the series of natural number $1, 2, 3, 4, ...$ has generating function $\frac{1}{(1-x)^2}$
Natural numbers : $\{1, 2, 3, 4, ...\}$ has GF $\frac{1}{(1-x)^2} = \frac{1}{1-2x-x^2}$ and has recurrence $S_n = 2S{n-1}-S_{n-2}$.
We can see that relationship more clearly if we rewrite the recurrence in this form:
$$S_n - 2S_{n-1} + S_{n-2} = 0$$And compute that with the denominator of the GF, namely:
$$1-2x+x^2$$We normally are interested not just in counting combinatorial structures, but also in analyzing their properties. We look at how to use bivarite generative functions for this purpose, and how this relates to the use of probability generating functions.
Definition Given a sequence $a_0, a_1, a_2, ..., a_k, ...$, the function
$$A(z) = \sum_{k \geq 0} a_k z^k$$is called the Ordinary Generating Function (OGF) of the sequence. We used notation the notation $\lfloor z^k \rfloor A(z)$ to refer to the coefficient $a_k$.
Given generating functions $A(z) = \sum_{k \geq 0} a_k z^k$ and $B(z) = \sum_{k \geq 0} b_k z^k$ that represent the sequence $\{a_0, a_1, ..., a_k, ...\}$ and $\{b_0, b_1, ... , b_k, ...\}$, respectively, we can perform a number of simple transformations to get generating functions for other sequences. Several such operations are show is Table 2. Example of the apllication of these operations may be found in the relationships among the entries in Table 1 that are valid for |z|<1.
| OGF | Sequence |
|---|---|
| $\sum_{N \geq 0} z^N = \frac{1}{1-z}$ | $1, 1, 1, , ..., 1, ...$ |
| $\sum_{N \geq 1} N z^N = \frac{z}{(1-z)^2}$ | $0, 1, 2, 3, 4, ..., N, ...$ |
| $\sum_{N \geq 2} {N \choose 2} z^N = \frac{z^2}{(1-z)^3}$ | $0, 0, 1, 3, 6, 10, ..., {N \choose 2}$ |
| $\sum_{N \geq M} {N \choose M} z^N = \frac{z^M}{(1-z)^{M+1}}$ | $0, ..., 0, 1 , M+1, ..., {N \choose M}$ |
| $\sum_{N \geq 0}{M \choose N} z^N = (1+z)^M$ | $1, M + 1, {M \choose 2} ..., (M \choose N), ..., M, 1$ |
| $\sum_{N \geq 0} {N+M \choose N} z^N = \frac{1}{(1-z)^{M+1}}$ | $1, M+1, {M+2 \choose 2}, {M+3 \choose 3}, ...$ |
| $\sum_{N \geq 0} z^{2N} = \frac{1}{1-z^2}$ | $1, 0, 1, 0, ..., 1, 0, ...$ |
| $\sum_{N \geq 0} c^N z^N = \frac{1}{1-cz}$ | $1, c, c^2, c^3, ..., c^N, ...$ |
| $\sum_{N \geq 0} \frac{z^N}{N!} = e^z$ | $1, 1, \frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}, ..., \frac{1}{N!}, ...$ |
| $\sum_{N \geq 1} \frac{z^N}{N} = ln\frac{1}{1-z}$ | $0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, ..., \frac{1}{N}, ...$ |
| $\sum_{N \geq 1} H_N z^N = \frac{1}{1-z}ln\frac{1}{1-z}$ | $0, 1, 1 + \frac{1}{2}, 1 + \frac{1}{2} + \frac{1}{3}, ..., H_N, ...$ |
| $\sum_{N \geq 0} N(H_N - 1)z^N = \frac{z}{(1-z)^2}ln\frac{1}{1-z}$ | $0, 0, 1, 3(\frac{1}{2}+\frac{1}{3}), 4(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}), ... $ |
Table 1. Elementary generating function
| OGF Operation | Sequence |
|---|---|
| $A(z) = \sum_{n \geq 0}z_n z^n$ | $a_0, a_1, a_2, ..., a_n, ...$ |
| $B(z) = \sum_{n \geq 0}b_n z^n$ | $b_0, b_1, b_2, .., b_n, ...$ |
| right shift $zA(z) = \sum_{n \geq 1}a_{n-1}z^n$ |
$0, a_0, a_1, a_2, ..., a_{n-1}, ...$ |
| left shift $\frac{A(z)-a_0}{z} = \sum_{n \geq 0} a_{n+1}z^n$ |
$a_1, a_2, a_3, ..., a_{n+1}, ...$ |
| index multiply (differentiation) $A'(z) = \sum_{n \geq 0}(n+1)a_{n+1}z^n$ |
$a_1, 2a_2, ..., (n+1)a_{n+1}, ...$ |
| index divide (integration) $\int_{0}^{z} A(t)dt = \sum_{n \geq 1} \frac{a_{n-1}}{n}z^n$ |
$0, a_0, \frac{a_1}{2}, \frac{a_2}{3}..., \frac{a_{n-1}}{n}, ...$ |
| scaling $A(\lambda z) = \sum_{n \geq 0} {\lambda}^n a_n z^n$ |
$a_0, \lambda a_1, \lambda^2 a_2, ..., \lambda^n a_n, ...$ |
| addition $A(z) + B(z) = \sum_{n \geq 0} (a_n + b_n)z^n$ |
$a_0+b_0, ..., a_n + b_n, ...$ |
| difference $(1-z)A(z) = a_0+\sum_{n \geq 1}(a_n-a_{n-1})z^n$ |
$a_0, a_1-a_0, ..., a_n-a_{n-1}, ...$ |
| convolution $A(z)B(z) = \sum_{n \geq 0}\big(\sum_{0 \le k \leq n} a_kb_{n-k} \big) z^n$ |
$a_0b_0, a_1b_0 + a_0b_1, ..., \sum_{0 \leq k \leq n} a_kb_{n-k}, $ |
| partial sum $\frac{A(z)}{1-z} = \sum_{n \geq 0} \big(\sum_{0 \leq k \leq n} a_k \big) z^n$ |
$a_1, a_1+a_2, ..., \sum_{0 \leq k \leq n} a_k, ...$ |
Table 2. Operation on OGF
If two sequences $a_0, a_1, ..., a_k, ...$ and $b_0, b_1, ..., b_k, ...$ are represented by the OGFs $A(z) = \sum_{k \geq 0} a_k z^k$ and $B(z) = \sum_{b \geq 0} b_k z^k$, respectively, then the operation given in table 2 produce OGFs that represent the indicated sequences. In particular:
$$\eqalign{ A(z) + B(z) \ \text{is the OGF for} \ a_0 + b_0, a_1 + b_1, a_2 + b_2, ...\\ zA(z) \ \text{is the OGF for} \ 0, a_0, a_1, a_2, ...\\ A'(z) \ \text{is the OGF for} \ a_1, 2a_2, 3a_3, ...\\ A(z)B(z) \ \text{is the OGF for} \ a_0b_0, a_0b_1 + a_1b_0, a_0b_2 + a_1b_1 + a_2b_0, ... }$$PROOF: Most of these are elementary and can be verified by inspection. The convolution operation (and the partial sum special case) are easily proved by manipulating the order of summation:
$$\eqalign{ A(z)B(z) &= \sum_{i \geq 0} a_iz^i \sum_{j \geq 0} b_j z^j\\ &= \sum_{i, j \geq 0} a_ib_jz^{i+j} &= \sum_{n \geq 0} \bigl(\sum_{0 \leq k \le n} a_k b_{n-k} \bigr) z^n }$$Taking $B(z) = \frac{a}{(1-z)}$ in this formula gives the partial sum operation. The convolution operation plays a special role in generating function manipulations, as we shall see.
Corollary: The OGF for the harmonic number is:
$$\sum_{N \geq 1} H_Nz^N = \frac{1}{1-z}ln\frac{1}{1-z}$$PROOF: Start with $\frac{1}{1-z}$ (the OGF for 1, 1, ..., 1, ...), integrate (to get the OGF for 0, 1, 1/2, 1/3, ..., 1/k, ...), and multiply by $\frac{1}{1-z}$. Similar examples may be found in the relationships among the enttries in Table 1.
Definition Given a sequence $a_0, a_1, a_2, ..., a_k, ...,$ the function:
$$A(z) = \sum_{k \geq 0} a_k \frac{z^k}{k!}$$is called the exponential generating function (EGF) of the sequence. We use the notation $k! \lfloor z^k \rfloor A(z)$ to refer to the coefficient $a_k$.
Table 3 gives a number of elementary exponential generating functions and table 4 gives some of the basic manipulations of EGFs.
| EGF | Sequence |
|---|---|
| $\sum_{N \geq 0} \frac{z^N}{N!} = e^z$ | $1, 1, 1, 1, ..., 1, ...$ |
| $\sum_{N \geq 1} \frac{z^N}{(N-1)!} = ze^z$ | $0, 1, 2, 3, 4, ..., N, ...$ |
| $\frac{1}{2} \sum_{N \geq 2} \frac{z^N}{(N-2)!} = \frac{1}{2}z^2 e^z$ | $0, 0, 1, 3, 6, 10, ..., {N \choose 2}, ...$ |
| $\frac{1}{M!} \sum_{N \geq M} \frac{z^N}{(N-M)!} = \frac{1}{M!} z^M e^z$ | $0, ..., 0, 1, M+1, ..., {N \choose M}, ...$ |
| $\sum_{N \geq 0} \frac{1+(-1)^N}{2} \frac{z^N}{N!} = \frac{1}{2}(e^z + e^{-z})$ | $1, 0, 1, 0, ..., 1, 0, ...$ |
| $\sum_{N \geq 0}\frac{c^Nz^N}{N!} = e^{cz}$ | $1, c, c^2, c^3, ..., c^N, ...$ |
| $\sum_{N \geq 0}\frac{z^N}{(N+!)!} = \frac{e^z-1}{z}$ | $1, \frac{1}{2}, \frac{1}{3}, ..., \frac{1}{N+1}, ...$ |
| $\sum_{N \geq 0}\frac{N!z^N}{N!} = \frac{1}{1-z}$ | $1, 1, 2, 6, 24, ..., N!, ...$ |
Table 3. Elementary exponential generating functions
| EGF Operation | Sequence |
|---|---|
| $A(z) = \sum_{n \geq 0}a_n \frac{z^n}{n!}$ | $a_0, a_1, a_2, ..., a_n, ...$ |
| $B(z) = \sum_{n \geq 0}b_n \frac{z^n}{n!}$ | $b_0, b_1, b_2, .., b_n, ...$ |
| right shift (integration) $\int_0^z A(t)d(t) = \sum_{n \geq 1}a_{n-1}\frac{z^n}{n!}$ |
$0, a_0, a_1, a_2, ..., a_{n-1}, ...$ |
| left shift (differentiation) $A'(z)= \sum_{n \geq 0} a_{n+1} \frac{z^n}{n!}$ |
$a_1, a_2, a_3, ..., a_{n+1}, ...$ |
| index multiply $zA(z) = \sum_{n \geq 0}na_{n-1}\frac{z^n}{n!}$ |
$0, a_0, 2a_1, 3_a, ..., na_{n-1}, ...$ |
| index divide $(A(z) - A(0)/z = \sum_{n \geq 1}\frac{a_{n+1}}{n+1} \frac{z^n}{n!})$ |
$a_1, \frac{a_2}{2}, \frac{a_3}{3}, ..., \frac{a_{n+1}}{n+1}, ...$ |
| addition $A(z) + B(z) = \sum_{n \geq 0} (a_n + b_n)\frac{z^n}{n!}$ |
$a_0+b_0, ..., a_n + b_n, ...$ |
| difference $A'(z)-A(z) = \sum_{n \geq 0}(a_{n+1}-a_n)\frac{z^n}{n!}$ |
$a_0+b_0, ..., a_n+b_n, ...$ |
| binomial convolution $A(z)B(z) = \sum_{n \geq 0}\big(\sum_{0 \le k \leq n} a_kb_{n-k} \big) \frac{z^n}{n!}$ |
$a_0b_0, a_1b_0 + a_0b_1, ..., \sum_{0 \leq k \leq n} {n \choose k} a_kb_{n-k}, $ |
| binomial sum $e^z A(z) = \sum_{n \geq 0} \big(\sum_{0 \leq k \leq n} {n \choose k} a_k \big) \frac{z^n}{n!}$ |
$a_0, a_0 + a_1, ..., \sum_{0 \leq k \leq n} {n \choose k} a_k, ...$ |
Table 4. Operation on EGF
If two sequences $a_0, a_1, ..., a_k, ...$ and $b_0, b_1, ..., b_k, ...$ are represented by the EGFs $A(z) = \sum_{k \geq 0} \frac{a_k z^k}{k!}$ and $B(z) = \sum_{k \geq 0} \frac{b_k z^k}{k!}$, respectively, then the operations given in Table 4 produce EGFs that represent the indicated sequences. In particular,
$$\eqalign{ A(z) + B(z) \ \text{is the EGF for} \ a_0 + b_0, a_1 + b_1, a_2 + b_2, ...\\ A'(z) \ \text{is the EGF for} \ a_1, a_2, a_3 ...\\ zA(z) \ \text{is the EGF for} \ 0, a_0, 2a_1, 3a_2, ...\\ A(z)B(z) \ \text{is the EGF for} \ a_0b_0, a_0b_1 + a_1b_0, a_0b_2 + a_1b_1 + a_2b_0, ... }$$PROOF: As for theorem 3.1, these are elementary and can be verified by inspection woth possible exception of binomial convolution, which is easily verified with OGF convolution:
$$\eqalign{ A(z)B(z) &= \sum_{n \geq 0} \sum_{0 \leq k \leq n} \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!}z^n\\ &= \sum_{n \geq 0} \sum_{0 \leq k \leq n} {n \choose k} a_k b_{n-k} \frac{z^n}{n!} }$$we can automatically convert from the OGF for a sequence to the EGF for the same sequence, and vice versa by using Laplace transformation.
Generating function provide a mechanical method for solving many recurrence realtions. Givn a recurrence describing some sequence ${a_n}_{n \geq 0}$, we can often develop a solution by carrying out the folowing steps:
The same methos applies for EGFs, where we multiply by $z^n / n!$ and sum on $n$ in the first step. Whether OGFs or EGFs are more convenient depends on the recurrence.
Theorem 3.3 (OGFs for linear recurrences)
If $a_n$ satiesfies the recurrence:
$$a_n = x_1 a_{n-1} + x_2 a_{n-2} + ... + x_t a_{n-t}$$for $n \geq t$, then the generating function $a(z) = \sum_{n \geq 0} a_n z^n$ is rational function $a(z) = f(z) / g(z)$, where the denominator polynomial is $g(z) = 1 - x_1 z - x_2 z^2 - ... - x_t z^t$ and the numerator polynomial is determined by the initial values $a_0, a_1, ..., a_{t-1}$.
PROOF. The proof follows the general paradigm for solving recurrences described at the beginning of this section. Multiplying both sides of the recurrence by $z^n$ and summing for $n \geq t$ yields:
$$\sum_{n \geq t} a_n z^n = x_1 \sum_{n \geq t} a_{n-1} z^n + ... + x_t \sum_{n \geq t} a_{n-t}z^n$$The left-hand side evaluates to $a(z)$ minus the generating polynomial of the initial values; the first sum on the right evaluates to $za(z)$ minus a polynomial, and so forth. This $a(z)$ satisfies:
$$a(z) - u_0(z) = (x_1 za(z) - u_1 (z)) + ... + (x_t z^t a(z) - u_t (z))$$where the polynomials $u_0(z), u_1(z), ..., u_t{z}$ are of degree at most $t-1$ with coefficients depending only on the initial values $a_0, a_1, ...., a_{t-1}$. This functional equation is linear.
Solving the equation for $a(z)$ gives the explicit form $a(z) = f(z)/g(z)$, where $g(z)$ has the form announced in the statement and:
$$f(z) \equiv u_0 (z) - u_1 (z) - ... - u_t (z)$$depends solely on the initial values of the recurrence and has degree less than $t$.
Solving the quicksort recurrence with an OGF
Since coefficients as polynomials, then implied relationship constraining the generating function is a differential equation.
Given number of comparisons used by quicksort:
$$NC_N = N(N+!) + 2 \sum_{1 \leq k \leq N} C_{k-1} \ \text{for} \ N \geq 1 \ \text{with} \ C_0 = 0 \quad (1)$$The generating function is:
$$C(z) = \sum_{N \geq 0} C_N z^N \quad (2)$$First, multiply both sides of (1) by $z^N$ and sum of $N$ to get:
$$\sum_{N \geq 1} N C_N z^N = \sum_{N \geq 1} N(N+1) z^N + 2 \sum_{N \geq 1} \sum_{1 \leq k \leq N} C_{k-1} z^N$$The left-hand side is $zC'(z)$ (differentiate both sides of (2) and multiply by $z$) and the first term on the right is $2z/(1-z)^3$ (see table 1). The remaining term, the double sum, is a partial sum convolution (see table 2) that evaluates to $zC(z)/(1-z)$. Therefore, our recurrence relationship correspons to a differential equation on the generating function is:
$$C'(z) = \frac{2}{(1-z)^3} + 2 \frac{C(z)}{1-z} \quad (3)$$We obtain the solution to this differential equation by solving the corresponding homogeneous equation $\rho '(z) = 2 \rho (z) / (1-z)$ to get an "integration factor" $\rho (z) = 1 / (1-z)^2$. This gives:
$$\eqalign{ ((1-z)^2 C(z))' &= (1-z)^2 C'(z) - 2(1-z)C(z)\\ &= (1-z)^2 \big(C'(z) - 2\frac{C(z)}{1-z} \big) = \frac{2}{1-z} }$$Integrating, we get the result:
$$C'(z) = \frac{2}{(1-z)^2}ln\frac{1}{1-z}$$Theorem 3.4 (Quicksort OGF)
The average number of comparisons used by quicksort for a random permutation is given by:
$$C_N = \lfloor z^N \rfloor \frac{2}{(1-z)^2} ln \frac{1}{1-z} = 2(N+1)(H_{N+1}-1)$$PROOF. Solving recurrences with OGFs, the to extract coefficients, differentiate the generating function for the harmonic numbers.
Expanding is a general mechanism for finding the associated sequence from explicit functional form of a generating function. As expanding gerataing functions means we take infinate series from a compact functional form into an infinate series of terms.
The Taylor Series permits us to expand a function $f(z)$ given its derivatives at 0:
$$f(z) = f(0)+f'(0)z+\frac{f''(0)}{2!}z^2+\frac{f'''(0)}{(3!)}z^3+\frac{f''''(0)}{4!}z^4+...$$Thus, by calculating derivatives, we can, in principle, find the sequence associated with any given generating function.
In priciple, we can always compute generating function coefficients by direct application of Taylor's theorem, but the process can become too complex to be helpful. Most often, we expand a generating function by decomposing it into simpler parts for which expansions are known. Indeed, this is the method of choice, and we will be using it extensively.
Generating functions succinctly represent infinite sequences. Ofter, their importance lies in the fact that simple manipulations on equations involving the generating function can lead to surprising relationships involving the underlying sequences that otherwise might be diffiult to derive. Several basic examples of this follow:
Vardermode's convolution
$$\sum_k {r \choose k}{s \choose {N-k}} = {{r+s} \choose N}$$is trivial to derive, as it is the convolution of coefficients that express the functional relation:
$$(1+z)^r (1+z)^s = (1+z)^{r+s}$$Quicksort recurrence
Multiplying OGFs by $(1-z)$ corresponds to differencing the coefficients, as stated in table 2.
Fibonacci numbers
$$F(z) = \frac{z}{1-y} \quad \text{with} \ y = z+z^2$$Expanding this in terms of $y$, we have:
$$\eqalign{ F(z) = z \sum_{N \geq 0} y^N &= z \sum_{N \geq 0} (z+z^2)^N\\ &= \sum_{N \geq 0} \sum_{k} {N \choose k} z^{N+k+1} }$$But $F_N$ is simply the coefficient of $z^N$ in this, so we must have:
$$F_N = \sum_k {{N-k-1} \choose k}$$a well-known relationship between Fibonacci numbers and diagonals in Pascal's triangle.
Binomial transform
If $a^n = (1-b)^n$ for all $n$, then, obviously, $b^n = (1-a)^n$. Surprisingly, this generalizes to arbitary sequences: given two sequences $\{a_n\}$ and $\{b_n\}$ related according to the equation:
$$a_n = \sum_k {n \choose k} (-1)^k b_k$$we know that associated generating functions satisfy $B(-z) = e^z A(z)$. But then, of course, $A(-z) = e^zB(z)$, which implies that:
$$b_n = \sum_k {n \choose k} (-1)^k a_k$$In the analysis of algorithms, recursion in an algorithm (or recurrence relationships in its analysis) very often leads to functional equations on the corresponding generating functions. In other cases, we may be able to use the functional equation to determine the asymptotic behavior without ever finding an explicit form for the generating function, or to transform the problem to a similar form that can be more easily solved.
Linear
$$f(z) = zf(z) + z^2 f(z) + z$$Nonlinear
Catalan Number $$f(z) = zf(z)^2 + 1$$
GF for tree $$f(z) = ze^{f(z)}$$
Differential
Quicksort $$f'(z) = \frac{2}{(1-2)^3} + 2 \frac{2}{1-z'}$$
Compositional
Binary tries and radix-exchange sort: $$f(z) = e^{z/2} f(z/2)$$
Counts 2-3 trees $$f(z) = z + f(z^2 + z^3)$$
As with recurrences, the techniques of iteration, simply applying the equation to itself successively, can often be useful in determining the nature of a generating function defined by a function equation. For example:
$$f(z) = e^z f(z/2)$$Then, provided that //(f(0) = 1//), we must have:
$$\eqalign{ f(z) &= e^z e^{z/2} f(z/4)\\ &= e^z e^{z/2} e^{z/4} f(z/8)\\ &.\\ &.\\ &.\\ &= e^{z+z/2+z/4+z/8+...}\\ &= e^{2z} }$$This proves that //(2^n//) is the solution to the recurrence:
$$f(n) = \sum_{k} {n \choose k} \frac{f_k}{2^k} \quad \text{for} \ n>0 \ \text{with} \ f_0=1$$This recurrence would be difficult to handle without generating functions:
$$C_N = N + 1 + \sum_{1 \leq k \leq N} \frac{(N-k)(k-1)}{{N \choose 3}} (C_{k-1} + C_{N-k}) \quad \text{for} \ N>2$$with $C_0 = C_1 = C_2 = 0$. $N+1$ as the number of comparions required to partition $N$ elements.
Multiplying by ${N \choose 3}$ and removing the symmetry in the sum, we have:
$${N \choose 3} C_N = (N+1) {N \choose 3} + 2 \sum_{1 \leq k \leq N}(N-k)(k-1)C_{k-1}$$Then, multiplying boyh sides by $z^{N-3}$ and summing on $N$ eventually leads to differential equation:
$$C'''(z) = \frac{24}{(1-z)^5} + 12 \frac{C'(z)}{(1-z)^2} \quad (5)$$Multiply both sides by $(1-z)^3$:
$$(1-z)^3 C'''(z) = 12(1-z)C'(z) + \frac{24}{(1-z)^2} \quad (6)$$Follow the Euler euqation, we can decompose it by rewriting it in in terms of an operator that both multiplies and differentiates:
$$\Psi C(z) \equiv (1-z)\frac{d}{dz} C(z)$$which allows us to rewrite (6) as:
$$\Psi (\Psi + 1)(\Psi + 2) C(z) = 12 \Psi C(z) + \frac{24}{(1-z)^2}$$Collecting all the terms involving $\Psi$ into one plynomial and factoring, we have:
$$\Psi (\Psi + 5)(\Psi - 2)C(z) = \frac{24}{(1-z)^2}$$The implication of this equation is that we can solve for $C(z)$ by successively solving three first-order differential equations:
$$\Psi U(z) = \frac{24}{(1-z)^2} \ \text{or} \ U'(z) = \frac{24}{(1-z)^{3}},$$$$(\Psi+5) T(z) = U(z) \ \text{or} \ T'(z) = -5 \frac{T(z)}{(1-z)} + \frac{U(z)}{1-z'},$$$$(\Psi-2) C(z) = T(z) \ \text{or} \ C'(z) = 2 \frac{C(z)}{(1-z)} + \frac{T(z)}{1-z},$$Theorem 3.5 (Median-of-three Quicksort)
The average number of comparions used by median-of-three quicksort for a random permutation is given by:
$$C_N = \frac{12}{7}(N+1)\big(H_{N+1} - \frac{23}{14} \big) \quad \text{for} \ N \geq 6$$PROOF:
$$\eqalign{U(z)=\frac{12}{(1-z)^2}-12;\\ T(z) = \frac{12}{7} \frac{1}{(1-z)^2} - \frac{1}{5} + \frac{24}{35}(1-z)^5;\\ C(z) = \frac{12}{7} \frac{1}{(1-z)^2} ln \frac{1}{1-z} - \frac{54}{49} \frac{1}{(1-z)^2} + \frac{6}{5} - \frac{24}{245}(1-z)^5;}$$For instance, the above analysis shows that we save about 14% of the cost of comparisons by using the median-of-three variant for quicksort, and a more detailed analysis, taking into account the extra costs, shows that bigger samples lead to marginal further improvements.
Generating functions as analytic tools for solving recurrence relationships, can be also provide a way to count combinatorial objects systematically. The "Combinatorial objects" may be data structures being operated upon by algorithms, so this process plays a fundamental role in the analysis of algorithms as well.
For example, a recursive data structure "binary tree" appear in many problems in combinatorics and the analysis of algorithms, for example, if internal nodes correspond to two-argument arithmetic operators and external nodes correspond to variables, the binary trees correspond to arithmetic expression. The question is, how many binary trees are there with N external nodes?
Counting binary trees
One way to proceed is to define a recurrence. Let $T_N$ be the number of binary trees with $N+1$ external nodes. Just by drawing, we know that $T_0 = 1, T_1 = 1, T_2 = 2, T_3 = 5, \ \text{and} \, T_4 = 14$. Now, we can derive a recurrence from the recursive definition; if the left subtree in a binary tree with $N+1$ external nodes has $k$ external nodes (there are $T_{k-1}$ different such trees), then the right subtree must have $N-k+1$ external nodes (there are $T_{N-k}$ possibilities), so $T_n$ must satisfy:
$$T_N = \sum_{1 \leq k \leq N} T_{k-1} T_{N-k} \quad \text{for} \ N>0 \ \text{with} \ T_0 = 1$$This is simple convolution: multiplying by $z^N$ ad summing on $N$, we find that the corresponding OGF must satisfy the nonlinear functional equation:
$$T(z) = zT(z)^2 + 1$$This formula for $T(z)$ is easily solved with the quadratic equation:
$$zT(z) = \frac{1}{2} (1 \pm \sqrt{1-4z})$$To get equality when $z=0$, we taje the solution with a minus sign.
Theorem 3.6 (OGF for binary trees)
The number of binary trees with $N+1$ external nodes is given by the Catalan numbers:
$$T_N = \lfloor Z^{N+1} \rfloor \frac{1-\sqrt{1-4z}}{2} = \frac{1}{N+1} {2N \choose N}$$PROOF. The explicit representation of OGF was derived earlier. To extent coefficients, use the binomial theorem with exponent $1/2$ (Newton's formula):
$$zT(z) = -\frac{1}{2} \sum_{N \geq 1} {1/2 \choose N} (-4z)^N$$Setting coefficients equal gives:
$$\eqalign{T_N &= -\frac{1}{2} {1/2 \choose {N + 1}} (-4)^{N+1}\\ &= -\frac{1}{2} \frac{\frac{1}{2}(\frac{1}{2} - 1)(\frac{1}{2} - 2)...(\frac{1}{2} - N)(-4)^{N+1}}{(N+1)!}\\ &= \frac{1.3.5...(2N - 1).2^N}{(N+1)!}\\ &= \frac{1}{N+1} \frac{1.3.5...(2N - 1)}{N!} \frac{2.4.6...2N}{1.2.3...N}\\ &= \frac{1}{N+1} {2N \choose N}}$$Counting binary trees (direct)
There is a simpler way to determine the explicit expression for the generating function above, which gives more insight into the instrict utility of generating functions for counting. We define $\tau$ to be the set of all binary trees, and adopt the notation $|t|$ to represntm for $t \in \tau$, the number of internal nodes in $t$. Then we have the following derivation:
$$\eqalign{T(z) &= \sum_{t \in \tau}z^{|t|}\\ &= 1 + \sum_{t_L \in \tau} \sum_{t_R \in \tau} z^{|t_L| + |T_R| + 1}\\ &= 1 + zT(z)^2}$$An application of generating functions that is directly related to the analysis of algorithms is their use for manipulating probabilities, to simplify the calculation of averages and variances.
Definition
Given a random variabel $X$ that takes on only nonnegative integer values, with $p_k \equiv P_r\{X = k\}$, the function $P(u) = \sum_{k \geq 0} p_k u^k$ is called the probability generating function (PGF) for the random variable.
Definition
The expected value of $X$, or $E(x)$, also known as the mean value of $X$, is defined to be $\sum_{k \geq 0} kp_k$. In terms of $r_k \equiv Pr\{X \leq k\}$, this is equivalent to $E(x) = \sum_{k \geq 0} (1-r_k)$. The variance of $X$, or var(X), is defined to be $\sum_{k \geq 0} (k - E(X))^2 p_k$. The standard deviation of $X$ is defined bo be $\sqrt(var(X))$.
Probability generating functions are important because they can probvide a way to find the average and the variance without tedious calculations involving discrete sums.
Theorem 3.7 (Mean and variabce from PGFs)
Given a PGF $P(z)$ for a random variable $X$, the expected value of $X$ is given by $P'(1)$ with variance $P''(1) + P'(1) - P'(1)^2$.
PROOF. If $P_k \equiv P_r\{X = k\}$, then:
$$P'(1) = \sum_{k \geq 0} kp_k u^{k-1}|_{u=1} = \sum_{k \geq 0} kp_k$$the expected value, by definition. Similarly, nothing that $P(1) = 1$, the stated result for the variance follows directly from the definition:
$$\eqalign{\sum_{k \geq 0}(k - P'(1))^2 p_k &= \sum_{k \geq 0} k^2p_k - 2\sum_{k \geq 0}kP'(1)p_k + \sum_{k \geq 0} P'(1)^2 p_k\\ &= \sum_{k \geq 0} k^2 p_k - P'(1)^2 = p''(1) + P'(1) - P'(1)^2}$$The quantity $E(X^r) = \sum_{k} k^r p_k$ is known as the rth moment of X. The expected value is the first moment and the variance is the difference between the second moment and the square of the first.
Binomial distribution
Consider a random string of $N$ independent bits, where each bit is 0 with probability $p$ and 1 with probability $q=1-p$. We can argue that the probability that exactly $k$ of the $N$ bits are 0 is:
$${N \choose k} p^k q^{N-k},$$so the corresponding PGF is:
$$P_N(u) = \sum_{0 \leq k \leq N} {N \choose k} p^k q^{N-k} u^k = (pu + q)^N$$Alternatively, we could observe that PGF for 0s in a single bits in $(pu+1)$ and the N bits are independent, so the PGF for the number of 0s in the $N$ bits is $(pu+q)^N$. Now, the average number of 0s is $P'(1) = pN$ and the variance is $P''(1) + P'(1) - P'(1)^2 = pqN$, and so forth. We can make these calculations easily without ever explicitly determining individual probabilities.
We use bivariate generating functions to get know values of various parameters relating to the structures.
Definition
Given a doubly sequence $\{a_{nk}\}$, the function:
$$A(z, u) = \sum_{n \geq 0} \sum_{k \geq 0} a_{nk} z^n u^k$$is called the bivarite generating function (BGF) of the sequence. We use notation $\lfloor z^n u^k \rfloor A(z, u)$ to refer to $a_{nk}$; $\lfloor z^n \rfloor A(z, u)$ to refer to $\sum_{k \geq 0} a_{nk} u^k$; and $\lfloor u^k \rfloor A(z, u)$ to refer to $\sum_{k \geq 0} a_{nk} z^n$.
As appropriate, a BGF may need to be made "exponential" by deviding by $n!$. Thus the exponential BGF of $\{a_{nk}\}$ is:
$$A(z, u) = \sum_{n \geq 0} \sum_{k \geq 0} a_{nk} \frac{z^n}{n!} u^k$$Definition
Let $\Rho$ be a class of combinatial structures with BGF $P(z, u)$. Then the function:
$$\frac{\partial P(z, u)}{\partial u}|_{u=1} = \sum_{p \in \mathrm{P}} cost(p)z^{|p|}$$is defined to be the cumulative generating function (CGF) for the class. Also let $\mathrm{P}_n$ denote the class of all the structure of size n in $\mathrm{P}$. Then the sum:
$$\sum_{p \in \mathrm{P}_n} cost(p)$$is defined to be the cumulated cost for the structure of size n. The cumulated cost is sometimes referred to as the unnormalized mean, since the true mean is obtained by "normalizing", or deviding by the number of structure of size n
Theorem 3.8 (BGFs and average costs)
Given a BGF $P(z, u)$ for a class of combinatorial structures, the average cost for all structure of a given size is given by the cumulated cost divided by the number of structures, or:
$$\frac{\lfloor z^n \rfloor \frac{\partial P(z, u)}{\partial u}|_{u=1}}{\lfloor z^n \rfloor P(1, z)}$$Proof. The calculations are strightforward, following directly from observation that $p_n(u)/p_n(1)$ is the associated PGF, then apllying Theorem 3.7